//Given the root of a binary tree, imagine yourself standing on the right side o
//f it, return the values of the nodes you can see ordered from top to bottom. 
//
// 
// Example 1: 
//
// 
//Input: root = [1,2,3,null,5,null,4]
//Output: [1,3,4]
// 
//
// Example 2: 
//
// 
//Input: root = [1,null,3]
//Output: [1,3]
// 
//
// Example 3: 
//
// 
//Input: root = []
//Output: []
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the tree is in the range [0, 100]. 
// -100 <= Node.val <= 100 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
// 👍 485 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Binary Tree Right Side View
class P199BinaryTreeRightSideView {
    public static void main(String[] args) {
        Solution solution = new P199BinaryTreeRightSideView().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
            int max_depth = -1;

            Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
            Queue<Integer> depthQueue = new LinkedList<Integer>();
            nodeQueue.add(root);
            depthQueue.add(0);

            while (!nodeQueue.isEmpty()) {
                TreeNode node = nodeQueue.remove();
                int depth = depthQueue.remove();

                if (node != null) {
                    // 维护二叉树的最大深度
                    max_depth = Math.max(max_depth, depth);

                    // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                    rightmostValueAtDepth.put(depth, node.val);

                    nodeQueue.add(node.left);
                    nodeQueue.add(node.right);
                    depthQueue.add(depth + 1);
                    depthQueue.add(depth + 1);
                }
            }

            List<Integer> rightView = new ArrayList<Integer>();
            for (int depth = 0; depth <= max_depth; depth++) {
                rightView.add(rightmostValueAtDepth.get(depth));
            }

            return rightView;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}